|
Vizualizare solutie pentru problema:
string
Titlul problemei
| string
|
Grupa
| Grupa B
|
Problema numarul
| 2
|
Runda numarul
| 12
|
Solutie oficiala
| /* Mugurel Ionut Andreica -
Bucuresti, ROMANIA */
/* Time
Complexity: O(N*logN) - using binary tries
*/
#include #include
#include #define
filein "string.in" #define fileout
"string.out" #define maxn 500010 #define
maxl 19
typedef struct trie { trie
*pa,*pb; };
trie *root; char
s[maxn],found[maxl+1],stack[maxl+1],ch; long
i,j,k,m,n,l,memoc=maxn+2*maxl+4+1+28;
void
read(); void buildtrie(); void compute();
void print();
int main() {
read(); buildtrie(); compute();
print(); return 0; }
void
read() { FILE *fin=fopen(filein,"r");
fscanf(fin,"%ld%c",&n,&ch);
for (i=0;i {
fscanf(fin,"%c",&ch); s[i]=ch; }
s[n]=0; }
void inserttrie(long
start) { long i; trie *aa,*aux;
for (aa=root,i=start;i if (s[i]=='a') {
if (aa->pa!=NULL) aa=aa->pa;
else { aux=new trie;
aux->pa=NULL; aux->pb=NULL;
aa->pa=aux; aa=aux;
memoc+=sizeof(trie); } } else
{ if (aa->pb!=NULL) aa=aa->pb;
else { aux=new trie;
aux->pa=NULL; aux->pb=NULL;
aa->pb=aux; aa=aux;
memoc+=sizeof(trie); } } }
void buildtrie() { long i;
root=new trie; root->pa=NULL;
root->pb=NULL; memoc+=sizeof(trie);
for (i=0;i inserttrie(i);
}
void df(trie *po,long niv) {
if (po->pa==NULL) { l=niv+1;
for (i=0;i found[i]=stack[i];
found[niv]='a'; } else if
(po->pb==NULL) { l=niv+1; for
(i=0;i found[i]=stack[i];
found[niv]='b'; } else { if
(niv+2 { stack[niv]='a';
df(po->pa,niv+1); }
if (niv+2 { stack[niv]='b';
df(po->pb,niv+1); } } }
void compute() { l=100;
df(root,0); }
void print() {
long i;
freopen(fileout,"w",stdout);
printf("%ld\n",l);
for (i=0;i printf("%c",found[i]);
printf("\n");
/* printf("%ld\n",memoc); */
exit(0); }
Explicatii despre modul
de punctare
| 10 teste * 5 puncte
| |
Download
arhiva teste de intrare
Click aici pentru a va
intoarce |
© 2002 Vālsan Mihai Liviu Puteti trimite intrebari,
comentarii, sau sugestii la adresa liviuvalsan@yahoo.com |